// https://leetcode.cn/problems/repeated-substring-pattern/
// Created by ade on 2022/8/5.
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 暴力枚举法 48 ms	24 MB
    bool repeatedSubstringPattern1(string s) {
        int len = s.size();
        // i 代表的是份数
        for (int i = 2; i <= len; i++) {
            if (len % i != 0) continue;
            int subLen = len / i;
            string subStr = s.substr(0, subLen);
            int flag = 1;
            for (int j = 1; j < i; j++) {
                if (s.substr(j * subLen, subLen) != subStr) {
                    flag = 0;
                }
            }
            if (flag) return true;
        }
        return false;
    }

    // 不断的往后移动，如果移动到某个位置相等，则代表可以重复， 但是效率低的惊人 628 ms	677.6 MB
    bool repeatedSubstringPattern2(string s) {
        string s2 = s + s;
        int len = s.size();
        for (int i = 1; i < len / 2 + 1; i++) {
            if (s2.substr(i, len) == s) {
                return true;
            }
        }
        return false;
    }

    // 这种效率依然不高，但是内存占用确实小了很多，原理：斩头去尾，其实是上面的简化版 24 ms	13.1 MB
    bool repeatedSubstringPattern3(string s) {
        return (s + s).substr(1, s.size() * 2 - 2).find(s) != string::npos;
        // return (s + s).find(s, 1) != s.size(); 精简版 12 ms	11.7 MB
    };


};

int main() {
    string s = "aaaaaaaaaaaaa";
    Solution so;
    if (so.repeatedSubstringPattern(s))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    return 0;
}